{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Tastiness of Candy Basket"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumTastiness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #礼盒的最大甜蜜度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数数组 <code>price</code> ，其中 <code>price[i]</code> 表示第 <code>i</code> 类糖果的价格，另给你一个正整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>商店组合 <code>k</code> 类 <strong>不同</strong> 糖果打包成礼盒出售。礼盒的 <strong>甜蜜度</strong> 是礼盒中任意两种糖果 <strong>价格</strong> 绝对差的最小值。</p>\n",
    "\n",
    "<p>返回礼盒的 <strong>最大 </strong>甜蜜度<em>。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>price = [13,5,1,8,21,2], k = 3\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>选出价格分别为 [13,5,21] 的三类糖果。\n",
    "礼盒的甜蜜度为 min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8 。\n",
    "可以证明能够取得的最大甜蜜度就是 8 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>price = [1,3,1], k = 2\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>选出价格分别为 [1,3] 的两类糖果。 \n",
    "礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2 。\n",
    "可以证明能够取得的最大甜蜜度就是 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>price = [7,7,7,7], k = 2\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>从现有的糖果中任选两类糖果，甜蜜度都会是 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= k &lt;= price.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= price[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-tastiness-of-candy-basket](https://leetcode.cn/problems/maximum-tastiness-of-candy-basket/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-tastiness-of-candy-basket](https://leetcode.cn/problems/maximum-tastiness-of-candy-basket/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[13,5,1,8,21,2]\\n3', '[1,3,1]\\n2', '[7,7,7,7]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTastiness(self, price: List[int], k: int) -> int:\n",
    "        def can_reach(p, target, k):\n",
    "            cnt = 1\n",
    "            cur = p[0]\n",
    "            for i in range(1, len(p)):\n",
    "                if p[i] >= cur + target:\n",
    "                    cnt += 1\n",
    "                    cur = p[i]\n",
    "                if cnt >= k:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        price.sort()\n",
    "        l, r = 0, max(price)\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if can_reach(price, mid, k):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTastiness(self, price: List[int], k: int) -> int:\n",
    "        l, r = 0, max(price) - min(price)\n",
    "        price.sort()\n",
    "        if k == 2:\n",
    "            return r\n",
    "        ma = price.pop()\n",
    "        mi = price.pop(0)\n",
    "        def check(x):\n",
    "            res = [mi]\n",
    "            for p in price:\n",
    "                if p - res[-1] >= x and ma - p >= x:\n",
    "                    res.append(p)\n",
    "                    if len(res) == k - 1:\n",
    "                        return True\n",
    "                if ma - p < x:\n",
    "                    return False\n",
    "            return False\n",
    "        while l < r:\n",
    "            m = (l + r + 1) // 2\n",
    "            if check(m):\n",
    "                l = m\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return l\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTastiness(self, price: List[int], k: int) -> int:\n",
    "        price.sort()\n",
    "        def ctnum(numss: List[int], vv: int, kk: int) -> int:\n",
    "            preval  = numss[0]\n",
    "            ct      = 1\n",
    "            for val in numss:\n",
    "                if val >= preval + vv:\n",
    "                    ct += 1\n",
    "                    preval = val\n",
    "            return ct >= kk\n",
    "        \n",
    "        left, right = 0, (price[-1] - price[0]) // (k - 1) + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) >> 1\n",
    "            if ctnum(price, mid, k):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTastiness(self, price: List[int], k: int) -> int:\n",
    "        price.sort()\n",
    "        def check(d):\n",
    "            cnt=1\n",
    "            x0=price[0]\n",
    "            for x in price:\n",
    "                if x>=x0+d:\n",
    "                    cnt+=1\n",
    "                    x0=x\n",
    "            return cnt>=k\n",
    "\n",
    "        l=0\n",
    "        h=(price[-1]-price[0])//(k-1) +1\n",
    "        while l+1 < h:\n",
    "            m = (l+h)//2\n",
    "            if check(m):l=m\n",
    "            else: h=m\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTastiness(self, price: List[int], k: int) -> int:\n",
    "        price.sort()\n",
    "        # 绝对差最小值输入，返回是否存在k种类不同糖果满足条件\n",
    "        # 从排序后的 price 数组中从小到大取出 k个数，使得相邻两个数的差值至少为 x\n",
    "        def sweet(x):\n",
    "            # 最小值一定可以包括在里面？\n",
    "            pre = price[0]\n",
    "            count = 1\n",
    "            for i in range(1, len(price)):\n",
    "                if price[i]-pre >= x:\n",
    "                    count += 1\n",
    "                    pre = price[i]\n",
    "            return count >= k\n",
    "        \n",
    "        left, right = 0, price[-1] - price[0]\n",
    "        while left <= right:\n",
    "            mid = (left + right)//2\n",
    "            # print(left, mid, right, sweet(mid))\n",
    "            # 存在k种类的不同糖果打包满足条件，此时选择更大的甜蜜度\n",
    "            if sweet(mid):\n",
    "                res = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTastiness(self, price: List[int], k: int) -> int:\n",
    "        price = sorted(price)\n",
    "        def valid(diff):\n",
    "            count = 1\n",
    "            last = 0\n",
    "            for i in range(len(price)):\n",
    "                if price[i]-price[last]>diff:\n",
    "                    last= i\n",
    "                    count+=1\n",
    "                    if count>=k:\n",
    "                        return False\n",
    "            return True \n",
    "\n",
    "        return bisect_right(range((price[-1]-price[0])//(k-1)+1),0,key=valid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maximumTastiness(self, price: List[int], k: int) -> int:\n",
    "        n = len(price)\n",
    "        price.sort()\n",
    "        l, r = 0, price[n - 1] - price[0]\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) // 2\n",
    "            cnt = 1\n",
    "            start = 0\n",
    "            for i in range(1, n):\n",
    "                if price[i] - price[start] >= mid:\n",
    "                    start = i\n",
    "                    cnt += 1\n",
    "            if cnt >= k:\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTastiness(self, price: List[int], k: int) -> int:\n",
    "        def lb(arr,t):\n",
    "            start = 0\n",
    "            end = len(arr) - 1\n",
    "            while start <= end:\n",
    "                mid = (start + end) // 2\n",
    "                if arr[mid] >= t:\n",
    "                    end = mid - 1\n",
    "                else:\n",
    "                    start = mid + 1\n",
    "            return start\n",
    "        def check(mid):\n",
    "            x0 = price[0]\n",
    "            cnt = 1\n",
    "            for item in price:\n",
    "                if x0 + mid <= item:\n",
    "                    x0 = item\n",
    "                    cnt += 1\n",
    "            return cnt >= k\n",
    "            \n",
    "            \n",
    "        price.sort()\n",
    "        end = price[0] + price[-1] + 10\n",
    "        start = 0\n",
    "        while start <= end:\n",
    "            mid = (start + end) // 2\n",
    "            if check(mid):\n",
    "                start = mid + 1\n",
    "            else:\n",
    "                end = mid - 1\n",
    "        return end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumTastiness(self, price: List[int], k: int) -> int:\n",
    "        left = 0\n",
    "        right = (max(price) - min(price))//(k-1)\n",
    "        n = len(price)\n",
    "        price.sort()\n",
    "        if k == 2 :\n",
    "            return right\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            index = 0\n",
    "            for i in range(1,k):\n",
    "                if index < n:\n",
    "                    index = bisect_left(price,price[index]+mid)\n",
    "                else:\n",
    "                    break\n",
    "            if index > n-1:\n",
    "                right = mid - 1 \n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTastiness(self, price: List[int], k: int) -> int:\n",
    "        def check(midVal):\n",
    "            i = 0\n",
    "            n = len(price)\n",
    "            cnt = 1\n",
    "            while i < n and cnt <= k:\n",
    "                j = i\n",
    "                while j < n and price[j] - price[i] < midVal:\n",
    "                    j += 1\n",
    "                if j < n:\n",
    "                    cnt += 1\n",
    "                i = j\n",
    "            return cnt >= k\n",
    "\n",
    "        price.sort()\n",
    "        if k == 2:\n",
    "            return abs(price[-1] - price[0])\n",
    "        l = 0\n",
    "        r = price[-1]\n",
    "\n",
    "        # 二分转判定\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTastiness(self, price: List[int], k: int) -> int:\n",
    "        price.sort()\n",
    "        left, right = 0, price[-1] - price[0]\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            if self.check(price, k, mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n",
    "\n",
    "    def check(self, price: List[int], k: int, tastiness: int) -> bool:\n",
    "        prev = -inf\n",
    "        cnt = 0\n",
    "        for p in price:\n",
    "            if p - prev >= tastiness:\n",
    "                cnt += 1\n",
    "                prev = p\n",
    "        return cnt >= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTastiness(self, price: List[int], k: int) -> int:\n",
    "        price.sort(reverse=True)\n",
    "        def check(x:int)->bool:\n",
    "            pre=price[0]\n",
    "            cnt=1\n",
    "            for i in range(1,len(price)):\n",
    "                if pre-price[i]>=x:\n",
    "                    cnt+=1\n",
    "                    pre=price[i]\n",
    "                if cnt>=k: return True\n",
    "            return cnt>=k\n",
    "        l,r=0,(price[0]-price[-1])//(k-1)+1\n",
    "        while l+1<r:\n",
    "            mid=l+(r-l)//2\n",
    "            if check(mid):\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid\n",
    "        return l\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTastiness(self, price: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "        校验是否能够选择k个价格，使得甜蜜度大于等于tastiness\n",
    "        \"\"\"\n",
    "        def check(tastiness: int) -> bool:\n",
    "            cnt = 1             # 统计满足差值大于tastiness的价格数，初始price[0]肯定要选择\n",
    "            prev = price[0]     # 最后选择的元素初始为price[0]\n",
    "            for i in range(1, len(price)):\n",
    "                # 当前价格和记录的前一个价格的差值大于tastiness，说明当前价格能够被选择，选择数量+1\n",
    "                # 更新前一个价格为当前价格。因为价格是升序排序，与当前价格距离越近的一定差值越小。因此只要记录最后选中的价格，只要当前价格和最后选中的价格的差值大于tastiness\n",
    "                # 其他更早选中的价格的差值肯定更大，组成的礼盒的甜蜜度一定是大于tastiness的\n",
    "                if price[i] - prev >= tastiness:\n",
    "                    cnt += 1\n",
    "                    prev = price[i]\n",
    "            return cnt >= k     # 如果组成礼盒的糖果个数大于等于k，说明至少有k个价格能够满足甜蜜度大于等于tastiness\n",
    "\n",
    "        price = sorted(price)           # 对价格数组进行排序\n",
    "        left = 0                        # 对价格数组进行排序\n",
    "        right = price[-1] - price[0]    # 对价格数组进行排序\n",
    "        ans = 0                         # 最终答案\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2    # 最终答案\n",
    "            if check(mid):\n",
    "                # 校验成功，说明至少有k个价格能够满足甜蜜度大于mid，那么可以尝试搜索更大的甜蜜度\n",
    "                ans = mid       # 当前mid是一个潜在的答案，记录mid\n",
    "                left = mid + 1  # 修改下界，寻找更大的甜蜜度\n",
    "            else:\n",
    "                # 校验失败，说明无法找到k个价格来满足甜蜜度大于mid，那么应该尝试搜索更小的甜蜜度\n",
    "                right = mid - 1     # 修改上界\n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTastiness(self, price: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "        解题思路\n",
    "            当有一个函数可以计算在当前甜蜜度下元素的个数，这样就可以保证在大于等于k的时候是一个解，当小于这个值时不满足条件\n",
    "        :param price:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        price = sorted(price)\n",
    "\n",
    "        # 统计当前甜蜜度下可以获取到的元素个数\n",
    "        def count(k: int) -> int:\n",
    "            cnt, pre = 1, price[0]\n",
    "            for i in range(1, len(price)):\n",
    "                if price[i] - pre >= k:\n",
    "                    cnt += 1\n",
    "                    pre = price[i]\n",
    "            return cnt\n",
    "\n",
    "        left, right = 0, (price[-1] - price[0]) // (k - 1)+1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if count(mid) >= k:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTastiness(self, price: List[int], k: int) -> int:\n",
    "        price.sort()\n",
    "        l,r=0,price[-1]-price[0]+1 \n",
    "        def is_valid(mid,k):\n",
    "            c=0\n",
    "            prev=float('-inf')\n",
    "            for p in price:\n",
    "                if p-prev>=mid:\n",
    "                    c+=1    \n",
    "                    prev=p\n",
    "            return c>=k \n",
    "        while l+1<r:\n",
    "            print(l,r)\n",
    "            mid=(l+r)//2\n",
    "            if is_valid(mid,k):\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache,cache\n",
    "from string import *\n",
    "from itertools import product\n",
    "from collections import defaultdict\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def maximumTastiness(self, price: List[int], k: int) -> int:\n",
    "        price.sort()\n",
    "        n = len(price)\n",
    "        l = 0\n",
    "        r = price[-1] - price[0]\n",
    "        while l < r:\n",
    "            m = (l + r + 1) >> 1\n",
    "            p = price[0]\n",
    "            z = 1\n",
    "            for i in range(1,n):\n",
    "                if price[i] - p >= m:\n",
    "                    z += 1\n",
    "                    p = price[i]\n",
    "            if z >= k:\n",
    "                l = m\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return l"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
